package org.ruanjj.reorderlist;

import org.ruanjj.linkedlist.ListNode;

public class Solution {
    public void reorderList(ListNode head) {
        ListNode l1 = head;
        //取链表的后半段
        ListNode mid = midListNode(head);
        //反转后半段链表
        ListNode l2 = reverseList(mid.next);
        mid.next = null;

        ListNode l1_tmp;
        ListNode l2_tmp;
        while(l1 != null && l2 != null){
            l1_tmp = l1.next;
            l2_tmp = l2.next;

            l1.next = l2;
            l1 = l1_tmp;

            l2.next = l1;
            l2 = l2_tmp;
        }
    }

    private ListNode midListNode(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    ListNode cur = new ListNode(-1);
    ListNode pre = cur;
    private ListNode reverseList(ListNode head){
        //非递归的方式
    /*    ListNode pre = new ListNode(head.val);
        while(head.next != null){
           ListNode cur = new ListNode(head.next.val);
           head = head.next;
           cur.next = pre;
           pre = cur;
        }
        return pre;*/
        //递归的方式
        if(head == null){
            return null;
        }
        reverseList(head.next);
        cur.next = head;
        cur = cur.next;
        cur.next = null;
        return pre.next;
    }
}
